package com.example.demo.arithmetic.datastructure.tree;

//给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
//保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
//二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val ,
//Node.right 的任何后代的值 严格大于 Node.val。
//二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

//输入：preorder = [8,5,1,7,10,12]
//输出：[8,5,10,1,7,null,12]
public class Leetcode1008 {
    public TreeNode bstFromPreorder(int[] preorder) {
        // 第一个值 就是根节点
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 0; i < preorder.length; i++) {
            int val = preorder[i];
            insert(root, val);
        }
        return root;
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        if (val < node.val) {
            node.left = insert(node.left, val);
        }

        if (val > node.val) {
            node.right = insert(node.right, val);
        }
        return node;
    }
}
